/*
利用结点的右孩子指针将一个二叉树的叶子节点从左向右连接成一个单链表 (head 指向第一个，tail指向最后一个）
*/

#include <iostream>
#include "BiTreefun.h"
using namespace std;

// 二叉树生成单链表
void link(BTNode *p, BTNode *&head, BTNode *&tail)
{
  // 如果二叉树不为空
  if (p != NULL)
  {
    // 如果结点是叶子结点
    if (!p->lchild && !p->rchild)
    {
      // 针对第一个叶子结点 -- 初始化链表
      if (head == NULL)
      {
        head = p;
        tail = p;
      }
      
      // 其余情况，将叶子结点添加进链表
      else
      {
        tail->rchild = p;
        tail = p;
      }
    }
    
    // 左子树生成单链表
    link(p->lchild, head, tail);
    
    // 右子树生成单链表
    link(p->rchild, head, tail);
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 链表的头尾指针
  BTNode *head = NULL, *tail = NULL;
  
  // 生成单链表
  link(T, head, tail);
  
  // 遍历单链表
  while (head != NULL)
  {
    cout << head->data << " ";
    head = head->rchild;
  }
}